package class10_tree;

import java.util.Stack;

/**
 * 非递归方法实现二叉树的三种遍历
 */
public class Class03 {

    static class Node {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 非递归方式实现先序遍历
     *
     * @param node
     */
    public void pre(Node node) {
        // 头 左 右
        if (node != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(node);
            while (!stack.isEmpty()) {
                Node head = stack.pop();
                System.out.println(head.value);
                if (head.right != null) {
                    stack.push(head.right);
                }
                if (head.left != null) {
                    stack.push(head.left);
                }
            }
        }
        System.out.println("");
    }

    /**
     * 利用栈的特性，将二叉树上的每个节点，都压入栈中，然后再弹出
     *
     * @param node
     */
    public void in(Node node) {
        if (node != null) {
            Stack<Node> stack = new Stack<>();
            while (node != null || !stack.isEmpty()) {
                if (node != null) {
                    stack.push(node);
                    node = node.left;
                } else {
                    Node pop = stack.pop();
                    System.out.println(pop.value);
                    node = pop.right;
                }
            }
        }
        System.out.println("");
    }

    /**
     * 后续方法：利用两个栈实现后续遍历
     * 后续 ： 左右头
     *
     * @param node
     */
    public void pos01(Node node) {
        if (node != null) {
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(node);
            while (!s1.isEmpty()) {
                Node head = s1.pop();
                s2.push(head);
                if (head.left != null) {
                    s1.push(head.left);
                }
                if (head.right != null) {
                    s1.push(head.right);
                }
            }
            while (!s2.isEmpty()) {
                System.out.println(s2.pop());
            }
        }
    }

}
